import { IGridNode } from "./GameManager"; // 引入 IGridNode 接口定义

// A* 算法中用于内部计算的节点
class AStarNode {
    public x: number;
    public y: number;
    public gCost: number = 0; // 从起点到当前节点的代价
    public hCost: number = 0; // 从当前节点到终点的预估代价 (启发式)
    public parent: AStarNode | null = null;

    constructor(x: number, y: number) {
        this.x = x;
        this.y = y;
    }

    // fCost 是 gCost 和 hCost 的总和，是选择下一个节点的依据
    get fCost(): number {
        return this.gCost + this.hCost;
    }
}

export class AStar {

    /**
     * 查找从起点到终点的路径
     * @param startGridNode 起始网格节点
     * @param endGridNode 终点网格节点
     * @param grid 完整的 IGridNode 地图网格
     * @returns 返回一个包含路径上所有 IGridNode 节点的数组，如果找不到则返回 null
     */
    public static findPath(startGridNode: IGridNode, endGridNode: IGridNode, grid: IGridNode[][]): IGridNode[] | null {
        const gridWidth = grid.length;
        if (gridWidth === 0) return null;
        const gridHeight = grid[0].length;

        const openSet: AStarNode[] = [];   // 待考察的节点列表
        const closedSet: Set<string> = new Set(); // 已考察过的节点列表 (用 'x,y' 字符串做 key)

        const startNode = new AStarNode(startGridNode.x, startGridNode.y);
        const endNode = new AStarNode(endGridNode.x, endGridNode.y);

        openSet.push(startNode);

        while (openSet.length > 0) {
            // 1. 从 openSet 中找到 fCost 最低的节点
            let currentNode = openSet[0];
            for (let i = 1; i < openSet.length; i++) {
                if (openSet[i].fCost < currentNode.fCost || (openSet[i].fCost === currentNode.fCost && openSet[i].hCost < currentNode.hCost)) {
                    currentNode = openSet[i];
                }
            }

            // 2. 将当前节点从 openSet 移到 closedSet
            const currentIndex = openSet.indexOf(currentNode);
            openSet.splice(currentIndex, 1);
            closedSet.add(`${currentNode.x},${currentNode.y}`);

            // 3. 如果当前节点是终点，则回溯路径
            if (currentNode.x === endNode.x && currentNode.y === endNode.y) {
                return this.retracePath(currentNode, grid);
            }

            // 4. 遍历当前节点的邻居
            const neighbors = this.getNeighbors(currentNode, gridWidth, gridHeight);
            for (const neighborPos of neighbors) {
                const neighborGridNode = grid[neighborPos.x][neighborPos.y];

                // 如果邻居是障碍物或已在 closedSet 中，则跳过
                if (neighborGridNode.isObstacle || closedSet.has(`${neighborPos.x},${neighborPos.y}`)) {
                    continue;
                }

                const neighborNode = new AStarNode(neighborPos.x, neighborPos.y);
                const newMovementCostToNeighbor = currentNode.gCost + this.getDistance(currentNode, neighborNode);

                const existingNeighbor = openSet.find(node => node.x === neighborNode.x && node.y === neighborNode.y);

                // 如果新路径到邻居更短，或者邻居不在 openSet 中
                if (!existingNeighbor || newMovementCostToNeighbor < existingNeighbor.gCost) {
                    neighborNode.gCost = newMovementCostToNeighbor;
                    neighborNode.hCost = this.getDistance(neighborNode, endNode);
                    neighborNode.parent = currentNode;

                    if (!existingNeighbor) {
                        openSet.push(neighborNode);
                    }
                }
            }
        }

        // 如果 openSet 为空仍未找到路径，则说明无路可走
        return null;
    }

    // 回溯路径，从终点通过 parent 指针一直找到起点
    private static retracePath(endNode: AStarNode, grid: IGridNode[][]): IGridNode[] {
        const path: IGridNode[] = [];
        let currentNode: AStarNode | null = endNode;
        while (currentNode !== null) {
            path.push(grid[currentNode.x][currentNode.y]);
            currentNode = currentNode.parent;
        }
        return path.reverse(); // 反转数组，得到从起点到终点的路径
    }

    // 获取一个节点的邻居（上下左右及对角线）
    private static getNeighbors(node: AStarNode, gridWidth: number, gridHeight: number): {x: number, y: number}[] {
        const neighbors: {x: number, y: number}[] = [];
        for (let x = -1; x <= 1; x++) {
            for (let y = -1; y <= 1; y++) {
                if (x === 0 && y === 0) continue;

                const checkX = node.x + x;
                const checkY = node.y + y;

                if (checkX >= 0 && checkX < gridWidth && checkY >= 0 && checkY < gridHeight) {
                    neighbors.push({ x: checkX, y: checkY });
                }
            }
        }
        return neighbors;
    }

    // 计算两个节点之间的距离（启发式函数）
    private static getDistance(nodeA: AStarNode, nodeB: AStarNode): number {
        const dstX = Math.abs(nodeA.x - nodeB.x);
        const dstY = Math.abs(nodeA.y - nodeB.y);
        // 使用对角线距离作为启发式估算，14代表sqrt(2)*10，10代表直线距离
        if (dstX > dstY) {
            return 14 * dstY + 10 * (dstX - dstY);
        }
        return 14 * dstX + 10 * (dstY - dstX);
    }
}
